package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-03-14 09:54
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 以数组的第一个数为基数，从右到左进行比较，当高位的数小于基数时，将低位的数替换为高位的数
     * 从低位进行比较，将如果低位的数大于基数，将高位的数替换为低位的数，重复这个过程，直到高位和低位重合
     * 将低位的值设置为基数
     * 对低位左侧的数进行递归快速排序
     * 对低位右侧的数进行递归快速排序
     *
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end) {
        // 当数组只有一个元素时，结束递归
        if (start >= end) {
            return;
        }
        // 比较的基数
        int position = arr[start];
        // 初始化低位
        int low = start;
        // 初始化高位
        int high = end;
        // 当低位小于高位时，进行循环
        while (low < high) {
            // 当低位小于高位，并且高位的值大于基数时，一直移动高位的位置
            while (low < high && arr[high] >= position) {
                high--;
            }
            // 高位的值比基数小，将低位的值替换为高位的值
            arr[low] = arr[high];
            // 当低位小于高位，并且低位的值小于基数时，一直移动低位的位置
            while (low < high && arr[low] <= position) {
                low++;
            }
            // 低位的值大于基数，将高位的值替换为低位的值
            arr[high] = arr[low];
        }
        // 将低位的值替换为基数（此时低位和高位重合low = high）
        arr[low] = position;
        // 对低位左侧的数据进行递归排序
        quickSort(arr, start, low);
        // 对低位右侧的数据进行递归排序
        quickSort(arr, low + 1, end);


    }

}
